using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Dida
{
	/// <summary>
	/// <para>
	/// A convex polygon, that can have a any number of vertices.
	/// </para>
	/// <para>
	/// The vertices of this polygon should always be convex and planar.
	/// No checking to these contidions is performed though, so it
	/// is your task to make sure that they are met, when you are
	/// using functions like <see cref = "AddVertex">AddVertex</see>.
	/// If they are not, many methods won't work as expected.
	/// </para>
	/// </summary>
	public class Polygon
	{
		List<Vector3D> vertices = new List<Vector3D>();

		/// <summary>
		/// Creates an empty polygon object. Use functions like
		/// <see cref = "AddVertex">AddVertex</see> to add
		/// vertices to it.
		/// </summary>
		public Polygon()
		{
		}

		/// <summary>
		/// Creates a polygon from the given vertices
		/// </summary>
		/// <param name="verts">An array of <see cref = "Vector3D">Vector3D</see>'s,
		/// specifying the position of each vertex.</param>
		public Polygon(Vector3D[] verts)
		{
			vertices.AddRange(verts);
		}

		/// <summary>
		/// Creates a 3 vertex polygon, from the given vertices.
		/// </summary>
		/// <param name="v1">The first vertex</param>
		/// <param name="v2">The second vertex</param>
		/// <param name="v3">The third vertex</param>
		public Polygon(Vector3D v1, Vector3D v2, Vector3D v3)
		{
			vertices.Add(v1);
			vertices.Add(v2);
			vertices.Add(v3);
		}

		/// <summary>
		/// Creates a 4 vertex polygon, from the given vertices
		/// </summary>
		/// <param name="v1">The first vertex.</param>
		/// <param name="v2">The second vertex.</param>
		/// <param name="v3">The third vertex.</param>
		/// <param name="v4">The fourth vertex</param>
		public Polygon(Vector3D v1, Vector3D v2, Vector3D v3, Vector3D v4)
		{
			vertices.Add(v1);
			vertices.Add(v2);
			vertices.Add(v3);
			vertices.Add(v4);
		}

		/// <summary>
		/// Adds a vertex to this polygon.
		/// </summary>
		/// <param name="vert">The new vertex.</param>
		/// <remarks>
		/// This vertex will be placed between the current last vertex, and the
		/// first vertex, so it's index will be the index of the current last 
		/// vertex, plus 1.
		/// </remarks>
		public void AddVertex(Vector3D vert)
		{
			vertices.Add(vert);
		}

		/// <summary>
		/// Creates a representation of this polygon, built up from triangles
		/// (3 vertex polygons).
		/// </summary>
		/// <returns>An array of Polygons, that will each have 
		/// exactly 3 vertices</returns>
		public Polygon[] Triangulate()
		{
			Polygon[] ret = new Polygon[vertices.Count - 2];

			// find two corners that are not flat
			int nCornersFound = 0;
			int[] flatCorners = new int[2];
			for (int i = 0; i < vertices.Count; i++)
			{
				if (!IsCornerFlat(i))
				{
					flatCorners[nCornersFound++] = i;
					if (nCornersFound == 2)
						break;
				}
			}

			int writePtr = 0;

			int vert1 = flatCorners[0];
			int vert2 = flatCorners[0] + vertices.Count;

			int end = flatCorners[1];

			if (end - vert1 > vert2 - end)
				vert1++;
			else
				vert2--;

			while (vert1 != end && vert2 != end)
			{
				// test which direction has the most edges left.
				if (end - vert1 > vert2 - end)
				{
					// "eat" an edge on the direction of vert1
					ret[writePtr++] = new Polygon(
						vertices[vert1 % vertices.Count],
						vertices[(vert1 + 1) % vertices.Count],
						vertices[vert2 % vertices.Count]);

					vert1++;
				}
				else
				{
					// "eat" an edge on the direction of vert2
					ret[writePtr++] = new Polygon(
						vertices[(vert2 - 1) % vertices.Count],
						vertices[vert2 % vertices.Count],						
						vertices[vert1 % vertices.Count]);

					vert2--;
				}
			}

			return ret;
		}

		/// <summary>
		/// Gets the plane of this triangle.
		/// </summary>
		public Plane Plane
		{
			get
			{
				// find a non flat corner
				for(int i = 0;i < vertices.Count;i++)
				{
					int prev = (i + vertices.Count - 1) % vertices.Count;
					int next = (i + 1) % vertices.Count;

					Vector3D dir1 = vertices[next] - vertices[i];
					Vector3D dir2 = vertices[prev] - vertices[i];

					if(Vector3D.DotProduct(dir1, dir2) > -.999f)
					{
						// this corner is not flat, so we can create
						// the plane now
						Vector3D normal = Vector3D.CrossProduct(dir1, dir2);
						normal.Normalize();
						float dist = -Vector3D.DotProduct(vertices[i], normal);
						return new Plane(normal, dist);
					}
				}

				Debug.Fail("Unreachable code reached");
				return default(Plane);
			}
		}

		/// <summary>
		/// Returns whether the given corner is a flat corner. A corner is
		/// a flat corner, when the angle between the leg to the previous
		/// vertex, and the leg to the next vertex is 180 degrees (or very
		/// close to it, to take floating point inaccuracy into account).
		/// </summary>
		/// <param name="i">The index of the vertex that's at the corner
		/// you want to test.</param>
		/// <returns>True when the corner is flat, false when it is not.</returns>
		public bool IsCornerFlat(int i)
		{
			int prev = (i + vertices.Count - 1) % vertices.Count;
			int next = (i + 1) % vertices.Count;

			Vector3D dir1 = vertices[prev] - vertices[i];
			Vector3D dir2 = vertices[next] - vertices[i];

			return Vector3D.DotProduct(dir1, dir2) < -.999f;
		}

		/// <summary>
		/// Gets the position of the vertex with the given index.
		/// </summary>
		/// <param name="i">The index of the vertex. This must be
		/// 0 &lt;= i &lt; <see cref="NVertices">NVertices</see>.</param>
		/// <returns>The position of the vertex</returns>
		public Vector3D GetVertex(int i)
		{
			return vertices[i];
		}

		/// <summary>
		/// Gets the number of vertices in this polygon.
		/// </summary>
		public int NVertices
		{
			get { return vertices.Count; }
		}

		/// <summary>
		/// <para>
		/// Splits the polygon by the given plane.
		/// </para>
		/// <para>
		/// Note that since the polygon
		/// is convex, each side will at most be a single polygon.
		/// It's not possible to split a polygon so that it will 
		/// have more than one seperate parts on one side.
		/// </para>
		/// </summary>
		/// <param name="plane">The plane by which you want to split the polygon.</param>
		/// <param name="front">Will be set to the front part of the splitted polygon,
		/// or null if the whole polygon was on the back of the plane.</param>
		/// <param name="back">Will be set to the back part of the splitted polygon,
		/// or null if the whole polygon was in front of the plane.</param>
		public void Split(Plane plane, out Polygon front, out Polygon back)
		{
			float[] vertexDists = new float[vertices.Count];
			PlaneSide[] vertexSides = new PlaneSide[vertices.Count];
			bool hasInFront = false;
			bool hasOnBack = false;
			for (int i = 0; i < vertices.Count; i++)
			{
				vertexDists[i] = plane.GetDist(vertices[i]);

				if (vertexDists[i] > .001f)
				{
					vertexSides[i] = PlaneSide.Front;
					hasInFront = true;
				}
				else if (vertexDists[i] < -.001f)
				{
					vertexSides[i] = PlaneSide.Back;
					hasOnBack = true;
				}
				else
					vertexSides[i] = PlaneSide.OnPlane;
			}

			if (!hasOnBack)
			{
				// if no vertices are on the back, then each vertex
				// is either in front of the plane, or on the plane.
				// We will simply send the whole polygon to the front polygon
				front = this;
				back = null;
				return;
			}
			else if (!hasInFront)
			{
				// no vertices are in front of the plane, so 
				// the whole polygon will go to the back.
				front = null;
				back = this;
			}
			
			// there are vertices on both the front and the back side,
			// so we have to split the polygon.
			front = new Polygon();
			back = new Polygon();
			for (int i = 0; i < vertices.Count; i++)
			{
				int next = (i + 1) % vertices.Count;

				switch (vertexSides[i])
				{
					case PlaneSide.Front:
						front.AddVertex(vertices[i]);

						if (vertexSides[next] == PlaneSide.Back)
						{
							// if the current edge crosses the plane,
							// we have to interpolate the point, where it
							// crosses the plane, and add that to both polygons
							float t = -vertexDists[i] /
								(vertexSides[next] - vertexSides[i]);
							Vector3D onPlane = Vector3D.Interpolate(
								vertices[i], vertices[next], t);
							front.AddVertex(onPlane);
							back.AddVertex(onPlane);
						}
						break;
					case PlaneSide.Back:
						back.AddVertex(vertices[i]);

						if (vertexSides[next] == PlaneSide.Front)
						{
							// if the current edge crosses the plane,
							// we have to interpolate the point, where it
							// crosses the plane, and add that to both polygons
							float t = -vertexDists[i] /
								(vertexSides[next] - vertexSides[i]);
							Vector3D onPlane = Vector3D.Interpolate(
								vertices[i], vertices[next], t);
							front.AddVertex(onPlane);
							back.AddVertex(onPlane);
						}
						break;
					case PlaneSide.OnPlane:
						front.AddVertex(vertices[i]);
						back.AddVertex(vertices[i]);
						break;
				}
			}
		}

		/// <summary>
		/// Gets the bounding box of this polygon. The bounding box is the
		/// smallest box that contains the whole polygon.
		/// </summary>
		public Box BoundingBox
		{
			get
			{
				Box ret = new Box();
				ret.min = vertices[0];
				ret.max = vertices[0];

				for (int i = 1; i < vertices.Count; i++)
				{
					if (vertices[i].x < ret.min.x)
						ret.min.x = vertices[i].x;
					else if (vertices[i].x > ret.max.x)
						ret.max.x = vertices[i].x;

					if (vertices[i].y < ret.min.y)
						ret.min.y = vertices[i].y;
					else if (vertices[i].y > ret.max.y)
						ret.max.y = vertices[i].y;

					if (vertices[i].z < ret.min.z)
						ret.min.z = vertices[i].z;
					else if (vertices[i].z > ret.max.z)
						ret.max.z = vertices[i].z;
				}

				return ret;
			}
		}
	}
}